#include <heap.h>

void HeapInit(heap *h) {
  h->size = 0;
}

int HeapSize(heap *h) {
  return h->size;
}

int HeapEmpty(heap *h) {
  return h->size == 0;
}

void HeapTop(heap *h, heap_entry *out) {
  *out = h->q[0];
}

void HeapPop(heap *h) {
  int k = 0, cL, cR, c, s = h->size/2;
  heap_entry tmp;
  h->q[0] = h->q[--h->size];
  while (k < s) {
    cL = (k<<1)+1, cR = cL+1;
    c = cL;
    if (cR < h->size && (h->q[cR].priority < h->q[cL].priority))
      c = cR;
    if (h->q[k].priority < h->q[c].priority)
      break;
    tmp = h->q[k];
    h->q[k] = h->q[c];
    h->q[c] = tmp;
    k = c;
  }
}

void HeapPush(heap *h, heap_entry e) {
  int k = h->size, p;
  heap_entry tmp;
  h->q[h->size++] = e;
  while (k > 0) {
    p = (k-1)>>1;
    if (h->q[k].priority >= h->q[p].priority)
      break;
    tmp = h->q[k];
    h->q[k] = h->q[p];
    h->q[p] = tmp;
    k = p;
  }
}
